#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>


// FUNCTION: 定义动态数组
typedef int ElemType;

typedef struct {
	ElemType *elem;//存储元素的起始地址
	int TableLen;//元素个数
} SSTable;


// FUNCTION: 随机数生成
void ST_Init(SSTable &ST, int len) {
	// NOTE: 变量初始化
	// STEP: 多申请了一个位置,为了存哨兵
	ST.TableLen = len + 1;

	// STEP: 申请动态数组实际空间
	ST.elem = (ElemType *) malloc(sizeof(ElemType) * ST.TableLen);

	// STEP: 存放赋值变量是的索引
	int i;


	// NOTE: 生成随机数
	srand(time(NULL));


	// NOTE: 将数据存储到数组中
	// HINT: 为啥这里零号位置也存放了随机了数据？是为折半查找服务的。
	for (i = 0; i < ST.TableLen; i++) {
		ST.elem[i] = rand() % 100;
	}
}


// FUNCTION: 输出数组中全部元素
void ST_print(SSTable ST) {
	for (int i = 0; i < ST.TableLen; i++) {
		printf("%3d", ST.elem[i]);
	}

	printf("\n");
}


// FUNCTION: 折半插入排序（带哨兵）
// HINT: 我们认为一个序列部分有序范围是第1个元素到第n
void Binary_Insertion_Sort(ElemType A[], int n) {
	// NOTE: 变量声明
	int i, j, low, high, mid;


	// NOTE: 依次将A[2]〜A[n]插入前面的已排序序列
	for (i = 2; i <= n; i++) {
		// STEP: 认为索引值为i的元素是分界值，当他担任哨兵。赋值给A[0]
		A[0] = A[i];


		// STEP: 设置折半查找范围
		low = 1;
		high = i - 1;

		// STEP: 先通过二分查找找到待插入位置
		while (low <= high) {
			mid = (low + high) / 2;
			if (A[mid] > A[0]) {
				high = mid - 1;
			} else {
				low = mid + 1;
			}
		}

		// STEP: 待插入位置以及之后的位置，向后退一格
		for (j = i - 1; j >= high + 1; --j) {
			A[j + 1] = A[j];
		}

		// STEP: 待插入位置以及之后的位置，向后退一格
		A[high + 1] = A[0];
	}
}

// FUNCTION: 希尔排序
//多轮插入排序，考的概率很低，因为编写起来复杂，同时效率并不如快排，堆排
void ShellSort(ElemType A[], int n) {
	int dk, i, j;
	// 73 29 74 51 29 90 37 48 72 54 83
	for (dk = n / 2; dk >= 1; dk = dk / 2)//步长变化
	{
		for (i = dk + 1; i <= n; ++i)//以dk为步长进行插入排序
		{
			if (A[i] < A[i - dk]) {
				A[0] = A[i];
				for (j = i - dk; j > 0 && A[0] < A[j]; j = j - dk)
					A[j + dk] = A[j];
				A[j + dk] = A[0];
			}
		}
	}
}


int main() {
	setbuf(stdout, NULL);


	// NOTE: Variable declaration
	// STEP: 声明动态数组
	SSTable ST;

	// STEP: 声明一组数
	ElemType A[10] = {64, 94, 95, 79, 69, 84, 18, 22, 12, 78};


	// NOTE: 数组元素赋值
	// HINT: 实际申请了11个元素空间
	ST_Init(ST, 10);
	memcpy(ST.elem, A, sizeof(A));

	printf("Original sequence is: ");
	ST_print(ST);


	// NOTE: 折半插入排序
	Binary_Insertion_Sort(ST.elem, 10);

	// NOTE: 希尔排序
	ShellSort(ST.elem, 10);

	return 0;
}